1. Field of the Invention
The present invention relates to a node device having a label switching function and a method for setting up a label switched path.
2. Description of the Background Art
In a network layer protocol in which IP (Internet Protocol) nodes are inter-connected on a network, there is a scheme for realizing high speed packet transfer called MPLS (Multi-Protocol Label Switching).
In the MPLS, the label switching is carried out by allocating specific xe2x80x9clabelsxe2x80x9d to specific packet flows between nodes and setting an input side label and an output side label in correspondence at each node, so that the IP processing can be omitted and a high speed packet transfer can be realized. For example, in the case where the link layer is ATM, VPI(Virtual Path Identifier)/VCI (Virtual Channel Identifier) will be used as a label. A route through which the packet flow is label switched is called a label switched path. In the following description, the label switched path will be referred to simply as a path.
In the case of constructing the path, a label distribution protocol is used. The label distribution protocol exchanges control messages (path control messages) between nodes on a packet flow route in order to notify a correspondence between a flow identifier for identifying the packet flow in network global fashion and a label for identifying the packet flow in link local fashion.
In general, the path control message is transferred according to the layer 3 route information, but when the layer 3 route is looping, there are possibilities for the path control message to loop or a looping path to form.
In order to resolve this problem, there is a loop prevention method disclosed in xe2x80x9cInternet-Draft, draft-ohba-mpls-loop-prevention-00.txtxe2x80x9d, in which the ingress node information is contained in the path control message and each node stores the ingress node address (ingress node information) and the hop count from the ingress node for each branch on the input side of the path, and notifies to the downstream side the ingress node information which has the largest hop count from the ingress node among all the stored ingress node information along with the largest hop count +1. In addition, in the case of adding a new branch on the input side of the current path, or in the case of updating the ingress node information or the hop count from the ingress node for the existing input side branch, if the same ingress node information is already registered for another input side branch with respect to the same flow, it is judged that a loop will be formed so that the addition/updating of the input side branch is not carried out.
This loop prevention method has an advantage over the path vector scheme (in which each node that forwards the path control message adds its own address to the label allocation message and it is judged as a loop is the received label allocation message has the own address already written therein) in that the message length becomes fixed regardless of the hop count.
However, this loop prevention method has the following problem at a time of the route change.
For instance, consider a case where a path through a sequence of node devices R11xe2x86x92R12xe2x86x92R13xe2x86x92R14xe2x86x92R15xe2x86x92R16 on the layer 3 route is formed as shown in FIG. 1.
In this case, each node device on the path stores a flow identifier (flowid), an input link information (input physical link information (input interface)+input label)) for identifying the path, and xe2x80x9cR11xe2x80x9d as the ingress node information. The input link information (input link) is an information set in correspondence to the output link information (output link) and used in the label switching, which is obtained from a label obtained from the link identifier and an information on a physical link that exchanged the message. The physical link information will be denoted as Iij (i: an upstream node number of the link, j: a downstream node number of the link), and the link will be denoted as xe2x80x9cphysical link information: labelxe2x80x9d.
FIG. 2 shows the state of a flow table provided in the node device R15 in the case of the path shown in FIG. 1.
In this case, when the route change occurs at R12 and the next hop leading to Flowid=R16 is changed from R13 to R17, the label allocation release message (RELEASE message) specifying (flowid=R16, ingress=R11) is sent on the old route from R12, while the label allocation request message (SETUP message) specifying (flowid=R16, ingress=R11) is sent on the new route from R12.
Now, if the SETUP message reaches to R15 before the RELEASE message, another entry with flowid=R16 and ingress=R11 is already set in correspondence to the input link (I1516: x1516) when the SETUP message for the input link (I1715: x1715) is received, so that R15 judges that it is a loop even though it is actually not a loop.
As a result, the label allocation failure (SETUP_NACK) message will be returned from R15 to R17. At this point, R17 carries out the retransmission (retry) of the SETUP message after a prescribed period of time, but the retry would have to be repeated many times before the RELEASE message arrives from the old route if the retry interval is set too short, whereas a considerable amount of time would elapse before the path is switched to the new route if the retry interval is set too long. Yet, it is generally difficult to determine the optimum value for the retry interval, so that there is a need for a loop prevention mechanism that can minimize the need of the retry.
It is therefore an object of the present invention to provide a label switched path set up scheme which is capable of detecting a loop of the label switched path efficiently and quickly, and which can enable the switching of the label switched path even in the case where conventionally a label switch path loop would be erroneously detected at a time of the route change, without requiring a label set up retry operation from a previous hop node device of the node device that have erroneously detected the loop which would have been necessary conventionally.
According to one aspect of the present invention there is provided a method for setting up a label switched path, comprising the steps of: judging whether the label switched path forms a loop or not at a node that received a request message regarding a label switched path set up for a packet flow, on a basis of label switched path information stored in a first mode at said node that received the request message, the request message including a flow identifier for identifying the packet flow and information indicating that it is a message currently awaiting a response regarding the packet flow, and the first mode indicating that a message from which the label switched path information originates is a message currently awaiting a response; storing the flow identifier contained in the request message as the label switched path information in the first mode at said node device that received the request message, and transferring the request message from said node that received the request message to another node on a route of the packet flow, when said node that received the request message cannot judge that the label switched path does not form a loop; returning a response message for the request message from said node that received the request message when said node that received the request message judges that the label switched path does not form a loop; and changing the label switched path information currently stored in the first mode at a node that received the response message into a second mode different from the first mode such that the label switched path information that is changed into the second mode will not be used subsequently in judging whether any requested label switched path forms a loop or not at said node that received the response message and the label switched path will become available at said node that received the response message.
According to another aspect of the present invention there is provided a node device for setting up a label switched path, comprising: a judging unit configured to judge whether the label switched path forms a loop or not upon receiving a request message regarding the label switched path set up for a packet flow, on a basis of label switched path information stored in a first mode at a memory of said node device, the request message including a flow identifier for identifying the packet flow and information indicating that it is a message currently awaiting a response regarding the packet flow, and the first mode indicating that a message from which the label switched path information originates is a message currently awaiting a response; a first processing unit configured to store the flow identifier contained in the request message as the label switched path information in the first mode at the memory and transfer the request message to another node on a route of the packet flow, when the judging unit cannot judge that the label switched path does not form a loop, and to return a response message for the request message when the judging unit judges that the label switched path does not form a loop; and a second processing unit configured to change the label switched path information currently stored in the first mode at the memory into a second mode different from the first mode upon receiving the response message, such that the label switched path information that is changed into the second mode will not be used subsequently in judging whether any requested label switched path forms a loop or not at said node device and the label switched path will become available at said node device.
According to another aspect of the present invention there is provided a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a node device for setting up a label switched path, the computer readable program code means includes: first computer readable program code means for causing said computer to judge whether the label switched path forms a loop or not upon receiving a request message regarding the label switched path set up for a packet flow, on a basis of label switched path information stored in a first mode at a memory of said node device, the request message including a flow identifier for identifying the packet flow and information indicating that it is a message currently awaiting a response regarding the packet flow, and the first mode indicating that a message from which the label switched path information originates is a message currently awaiting a response; second computer readable program code means for causing said computer to store the flow identifier contained in the request message as the label switched path information in the first mode at the memory and transfer the request message to another node on a route of the packet flow, when the first computer readable program code means cannot judge that the label switched path does not form a loop, and to return a response message for the request message when the first computer readable program code means judges that the label switched path does not form a loop; and third computer readable program code means for causing said computer to change the label switched path information currently stored in the first mode at the memory into a second mode different from the first mode upon receiving the response message, such that the label switched path information that is changed into the second mode will not be used subsequently in judging whether any requested label switched path forms a loop or not at said node device and the label switched path will become available at said node device.